package 左哥算法.ch06二叉树;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

public class Ch03其他二叉树 {

    @Test
    public void test01(){
        Integer[] arr={2,2,2};
        TreeNode root = TreeNode.newLevelTree(arr);
        System.out.println(isValidBST01(root));
    }

    /**
     * ch01 判断是否是搜索二叉树，即左侧比自身小，右侧比自身大
     * 思路1：当二叉树中序遍历后，是从小到大有序的情况，则表示该二叉树是搜索二叉树
     */
    private int pre=Integer.MIN_VALUE;
    public boolean isValidBST01(TreeNode root) {
        if (root==null){
            return true;
        }
        boolean res;
        res= isValidBST01(root.left);
        if (!res||pre>=root.val){    //如果子节点不符合要求，或者上一个节点>=当前节点
            return false;
        }
        pre=root.val;
        res=res&& isValidBST01(root.right);
        return res;
    }

//    public int isValidBST02(){
//
//    }

    @Test
    public void test02(){
        Integer[] arr={2,1,3};
        TreeNode root = TreeNode.newLevelTree(arr);
        System.out.println(isEntirely(root));
    }

    /**
     * ch02:判断完全二叉树
     * 思路：
     * 层序遍历二叉树，遍历过程中只要存在一下两种情况，则表示该树不是完全二叉树
     *  有一个节点存在有右无左。
     *  有一个节点只有一个子节点，此节点之后的节点并不全是叶子节点。
     */
    public boolean isEntirely(TreeNode root){
        if (root==null){
            return true;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        boolean isLeaf=false;   //是否遇到左右孩子不全的情况
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            boolean left = node.left != null;
            boolean right = node.right != null;
            if (!left&&right){  //右侧存在左侧不存在
                return false;
            }
            if (isLeaf&&(left||right)){   //必须是叶子节点，但却还有子节点
                return false;
            }
            if (left){
                queue.add(node.left);
            }
            if (right){
                queue.add(node.right);
            }
            isLeaf=!left||!right;   //没有左子节点或右子节点的情况
        }
        return true;
    }

    @Test
    public void test03(){
        Integer[] arr={3,9,20,null,null,15,7};
        TreeNode root = TreeNode.newLevelTree(arr);
        System.out.println(isBalanced(root).isBalanced);
    }

    /**
     * ch03:判断平衡二叉树
     * 思路：
     *  先递归获取左右子树是否是平衡二叉树，并获取左右子树高度。（返回两个东西）
     *  如果左右子树是平衡二叉树，且左右子树高度相差小于等于1，则返回true和左右子树高度（高的那棵）
     */
    public ReturnType1 isBalanced(TreeNode root) {
        if (root==null){
            return new ReturnType1(true,0);
        }
        ReturnType1 l = isBalanced(root.left);
        if (!l.isBalanced){ //左侧不是平衡二叉树
            return new ReturnType1(false,l.height+1);
        }
        ReturnType1 r = isBalanced(root.right);
        if (!r.isBalanced){ //右侧不是平衡二叉树
            return new ReturnType1(false,r.height+1);
        }
        int max=Math.max(l.height,r.height),min=Math.min(l.height,r.height);
        //左右都是平衡二叉树，但高度差>1
        if (max-min>1){
            return new ReturnType1(false,max+1);
        }
        return new ReturnType1(true,max+1);
    }

    /**
     * ch04判断满二叉树
     */
    @Test
    public void test04(){
        TreeNode root1=new TreeNode();
        root1.newTree(5);
        Integer[] arr={1,2,3,4,5,null,7};
        TreeNode root2 = TreeNode.newLevelTree(arr);

        System.out.println(isFill(root1).isBalanced);
        System.out.println(isFill(root2).isBalanced);
    }

    /**
     *ch04：和ch03差不多的思路
     */
    public ReturnType1 isFill(TreeNode root){
        if (root==null){
            return new ReturnType1(true,0);
        }
        ReturnType1 l = isFill(root.left);
        ReturnType1 r = isFill(root.right);
        if (!l.isBalanced||!r.isBalanced){ //左右有一侧不是满二叉树
            return new ReturnType1(false,0);
        }
        if (l.height!=r.height){    //左右高度不统一
            return new ReturnType1(false,0);
        }
        return new ReturnType1(true,l.height+1);
    }

    class ReturnType1 {
        boolean isBalanced;
        int height;

        public ReturnType1(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }


    class ReturnType2{
        boolean isValidBST;
        int max;
        int min;
    }

    class ReturnType3{

    }
}
